package cn.xaut.查找表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class demo18 {

    // 双滑动窗口
    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if (len < 4)
            return res;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {

            // 去掉重复情况
            if (i > 0 && nums[i - 1] == nums[i])
                continue;

            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
                break;

            if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)
                continue;

            for (int j = i + 1; j < nums.length; j++) {

                // 去掉重复情况
                if (j > i + 1 && nums[j - 1] == nums[j])
                    continue;

                if (nums[i] + nums[j] > 0)
                    break;

                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
                    break;

                if (nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target)
                    continue;

                int l = j + 1, r = len - 1;
                while (l < r) {
                    int sum = nums[l] + nums[r] + nums[i] + nums[j];
                    if (sum == target) {
                        res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[l], nums[r])));
                        l ++;
                        r --;
                        while (l < r && nums[l] == nums[l - 1])
                            l++;
                        while (l < r && nums[r] == nums[r + 1])
                            r--;
                    } else if (sum > target)
                        r--;
                    else // sum < target
                        l++;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {

        List<List<Integer>> res = new demo18().fourSum(new int[]{-2, -1, -1, 1, 1, 2, 2}, 0);
        for (List<Integer> list : res)
            System.out.println(list);   // [[-2,-1,1,2],[-1,-1,1,1]]

        List<List<Integer>> res2 = new demo18().fourSum(new int[]{0, 1, 5, 0, 1, 5, 5, -4}, 11);
        for (List<Integer> list : res2)
            System.out.println(list);   // [[-4,5,5,5],[0,1,5,5]]
    }
}
